package tree;

import com.sun.org.apache.xpath.internal.SourceTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BST<E extends Comparable<E>> {


    private class Node{
        public E e;
        public Node left;
        public Node right;

        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }

    }


    private Node root;
    private int size;

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    //为二分搜索树添加元素：递归
    public void add(E e){
        root = add(root,e);

    }

    //返回插入新节点后二分搜索树的根节点
    private Node add(Node node,E e){

        if(node == null){
            size++;
            return new Node(e);
        }

        if(e.compareTo(node.e) < 0){
            node.left = add(node.left,e);
        }else if(e.compareTo(node.e) > 0){
            node.right = add(node.right,e);
        }

        return node;
    }

    //二分搜索树——前序遍历
    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node node){
        if(node == null){
            return ;
        }

        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(){
        inOrder(root);
    }

    //中序遍历以node为根的二分搜索树，递归算法
    private void inOrder(Node node){
        if(node == null){
            return ;
        }

        inOrder(node.left);
        inOrder(node.right);
    }

    public void postOrder(){

    }

    private void postOrder(Node node){
        if(node == null){
            return ;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    //前序遍历-非递归算法，使用栈
    public void preOrderNR(){
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);

            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur != null){
                stack.push(cur.left);
            }
        }
    }

    //层序遍历/广度优先遍历
    public void levelOrder(){
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        while (!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.e);

            if(cur.left != null){
                q.add(cur.left);
            }

            if(cur.right != null){
                q.add(cur.right);
            }
        }
    }

    //查找二分搜索树中的最小值：左子树中，没有左孩子的节点，就是最小值
    public E minimum(){
        if(size == 0){
            //二分搜索树中没有元素
            throw new IllegalArgumentException("没有元素");
        }

        return minimum(root).e;
    }

    //返回Node为根的二分搜索树节点
    private Node minimum(Node node){
        if(node.left == null){
            return node;
        }

        return minimum(node.left);

    }

    //删除二分搜索树最小值节点，要注意该节点是叶子节点还是根节点
    public E removeMin(){
        E ret = minimum();
        removeMin();

        return ret;
    }
    //删除掉以node为根的二分搜索树中的最小节点
    //返回删除节点后的新二分搜索树的根
    private Node removeMin(Node node){
        if(node.left == null){
            Node rightNode = node.right;
            //删除元素
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }


    //查找二分搜搜树中，最大值节点
    public E maximum(){
        if(size == 0){
            throw new IllegalArgumentException("没有元素");
        }

        return maximum(root).e;
    }

   //返回二分搜索树中，最大值的根节点
   private Node maximum(Node node){
        if(node.right == null){
            return node;
        }
        return maximum(node.right);
   }

   //删除最大值的节点，返回删除节点后的新子树的根节点
   private Node removeMax(Node node){
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }







}
